package com.cn.codebrush.栈;

import java.util.LinkedList;

/**
 * @Author Boolean
 * @Date 2022/6/15 21:12
 * @Version 1.0
 */
public class 剑指Offer09用两个栈实现队列 {

    /**
     * 使用java的同学请注意，如果你使用Stack的方式来做这道题，会造成速度较慢；
     * 原因的话是Stack继承了Vector接口，而Vector底层是一个Object[]数组，那么就要考虑空间扩容和移位的问题了。
     * 可以使用LinkedList来做Stack的容器，因为LinkedList实现了Deque接口，
     * 所以Stack能做的事LinkedList都能做，其本身结构是个双向链表，扩容消耗少。
     * 但是我的意思不是像100%代码那样直接使用一个LinkedList当做队列，那确实是快，但是不符题意。
     * 贴上代码，这样的优化之后，效率提高了40%，超过97%。
     *
     * AbstractList<-AbstractSequentialList<-LinkedList，AbstractList<-Vector<-Stack，stack和linkedlist不是都从AbstractList继承来的吗？
     * 很好，终于有人来问这样的问题了。LinkedList直接继承于AbstractSequentialList，也就是直接继承于顺序表抽象类，
     * 这个有序表抽象类继承于列表抽象类(AbstractList)。 AbstractList提供了基本的列表操作，
     * 其的doc中写道：For sequential access data (such as a linked list),AbstractSequentialList should be used in preference to this class.
     * 也就是对于顺序表，需要优先继承于顺序表抽象类而非直接使用列表抽象类。 这个是在架构或者说是在思想层面上的解释，也解释了我为什么我这么说。
     * 就jdk源码层面来说 LinkedList本身维护了Node<E>类型的 first和last 头尾节点以实现双向链表的存储结构。
     * Vector 维护了一个 Object[]数组，并实现了对数组的各种操作，Stack只是根据栈的特性，提供了push\pop\peek\emty等方法，并调用父类(Vector)的方法来操作数组。
     * 所以在这个层面上来说，确实将我的说法中"而Vector底层是AbstractList，是一个数组"改为"而Vector底层是Object[]，是一个数组"更加稳妥。
     *
     * 官方建议的创建栈的方式是这样的
     * Deque<Integer> stack = new ArrayDeque<>();
     */




    class CQueue {
        LinkedList<Integer> stack1;
        public CQueue() {
            stack1 = new LinkedList<>();
        }

        public void appendTail(int value) {
            stack1.add(value);
        }

        public int deleteHead() {
            if (stack1.isEmpty()) return -1;
            return stack1.pop();

        }
    }
}
